# X质数(好题)

"""
本题的难点在于如何生成所有的子序列, 生成子序列的方法包括以下两种:
1. 通过位运算快速生成所有子序列(n较小时)
2. 使用DP来生成子序列(n较大时)

通过位运算快速生成所有子序列
一、子序列
子序列是从原字符串中选择任意数量的字符（可以是0个、1个、...、所有字符），且保持这些字符的原始顺序形成的字符串。
例如：原字符串 "abc" 的子序列包括 "a", "b", "c", "ab", "ac", "bc", "abc" 和空字符串 ""（共 2^3=8 种可能性）。

二、位掩码（Bitmask）
假设字符串长度为 n，我们可以用一个 n 位的二进制数 来表示是否选择某个字符：
二进制数的每一位对应原字符串的一个字符。如果某一位是 1，表示选择对应的字符；如果是 0，表示不选择。
例如，对于字符串 "abc"（n=3）：
二进制数 101（十进制5）表示选择第1个字符 "a" 和第3个字符 "c"，生成子序列 "ac"。
二进制数 010（十进制2）表示选择第2个字符 "b"，生成子序列 "b"。

三、遍历所有可能的二进制数
所有可能的二进制数范围是 0（全0）到 2^n - 1（全1）。例如，n=3时：
范围是 000（0）到 111（7），共 2^3=8 种可能。 每个二进制数对应一种子序列选择方式

四、如何将二进制数转换为子序列？
1. 外层循环遍历所有可能的二进制数：
    对于 n=3，遍历 1（001）到 7（111）。
2. 内层循环检查每一位是否为1：
    对于每个二进制数 mask，遍历其每一位 i（从0到n-1）。
    如果 mask 的第 i 位是1（即 mask & (1 << i) 为真），则将原字符串的第 i 个字符加入子序列。

通过DP快速生成所有子序列
def get_all_subsequences_dp(s):
    dp = set()
    for char in s:
        new_subseq = {sub + char for sub in dp}
        dp.update(new_subseq)
        dp.add(char)
    return list(dp)
"""
import math


def get_all_subsequences_mask(s):
    # 通过位运算快速生成所有子序列
    n = len(s)
    subsequences = set()
    for mask in range(1, 1 << n):  # 遍历1到2^n-1
        subseq = []
        for i in range(n):
            if mask & (1 << i):  # 检查第i位是否为1
                subseq.append(s[i])
        subsequences.add(''.join(subseq))
    return list(subsequences)


def get_all_subsequences_dp(s):
    # 通过DP快速生成所有子序列
    dp = set()
    for char in s:
        new_subseq = {sub + char for sub in dp}
        dp.update(new_subseq)
        dp.add(char)
    return list(dp)


def count_x_prime(n):
    def sieve(num):
        is_prime = [True] * (num + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(math.sqrt(num)) + 1):
            if is_prime:
                for j in range(i * i, num + 1, i):
                    is_prime[j] = False
        return {idx for idx, prime in enumerate(is_prime) if prime}

    primes = sieve(n)  # n以内的所有质数
    single_prime = ["2", "3", "5", "7"]  # 10以内的所有质数
    cnt = 0
    for num in range(1, n):  # 遍历所有数字
        # i为质数
        if num in primes:
            cnt += 1
            continue

        # i的其中一位是质数
        num_str = str(num)
        if any(c in num_str for c in single_prime):
            cnt += 1
            continue

        # 判断子序列中是否有质数
        sub_seq = set()  # 存储所有子序列
        for c in num_str:
            seq = {sub + c for sub in sub_seq}
            if any(int(sub) in primes for sub in seq):  # 检查子序列中是否包含质数
                primes.add(num)
                cnt += 1
                break
            sub_seq.update(seq)
            sub_seq.add(c)

    return cnt


def count_x_prime_mask(n):
    def is_prime(n):
        _nums = [True] * (n + 1)
        _nums[0] = _nums[1] = False
        for i in range(2, n):
            if _nums[i]:
                for j in range(i ** 2, n + 1, i):
                    _nums[j] = False
        return _nums

    primes = is_prime(n)
    ans = 0
    for num in range(n + 1):
        digits = [int(n) for n in str(num)]  # 将数字转换为一个十进制的列表 如 312 -> [3,1,2]
        length = len(str(num))
        for mask in range(1, 1 << length):
            subseq = 0
            for i in range(length):
                if mask & (1 << i):
                    subseq = subseq * 10 + digits[i]  # 将子序列拼接为数字
            if primes[subseq]:  # 如果子序列是一个质数
                primes[num] = True  # 在primes中定义该数为x质数
                ans += 1
                break
    return ans


if __name__ == '__main__':
    print(get_all_subsequences_dp("1234567"))
    print(get_all_subsequences_mask("1234567"))
    print(count_x_prime(1000000))  # 989457
    print(count_x_prime_mask(1000000))  # 989457
